package com.maishi.programmer.jainzhioffer;

import java.util.HashMap;

/**
 * 请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，
 * 而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。
 * 例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
 */
public class TestProblem19 {

    public boolean match(char[] str, char[] pattern) {
        if (str == null || pattern == null) return false;
        int strIndex = 0;
        int patternIndex = 0;
        return matchCore(str, strIndex, pattern, patternIndex);
    }

    private boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
        //如果匹配到尾成功
        if (strIndex == str.length && patternIndex == pattern.length) return true;
        //如果模式到尾,字符串没到尾,匹配失败
        if (strIndex != str.length && patternIndex == pattern.length) return false;
        //如果模式第二个字符是*
        if (patternIndex+1<pattern.length && pattern[patternIndex+1]=='*') {
        //第一个位置相同 或者 模式第一个位置为. 即任意字符
            if(str[strIndex]==pattern[patternIndex]&&strIndex!=str.length||pattern[patternIndex]=='.'&&strIndex!=str.length){
                //分三种情况递归
                return matchCore(str,strIndex,pattern,patternIndex+2)//匹配0个字符，即*前一个字符出现0次
                || matchCore(str, strIndex+1, pattern, patternIndex+2)//匹配1个字符，即*前一个字符仅出现1次
                || matchCore(str, strIndex+1, pattern, patternIndex);//匹配1个字符，模式保持不变
            } else {
                //第一个位置不匹配，模式后移两位  也就是视x*匹配0个字符
                return matchCore(str, strIndex, pattern, patternIndex+2);
            }
        }
        //第一个字符匹配，但模式第二个不是* 模式和字符串上都后移一位 <strong>情况a1</strong>
        if(strIndex!=str.length&&(str[strIndex]==pattern[patternIndex]||pattern[patternIndex]=='.')){
            return matchCore(str, strIndex+1, pattern, patternIndex+1);
        }else{
            return false;//第一个字符不匹配并且模式第二个位置不是* <strong>情况a2</strong>
        }
        //HashMap map = new HashMap();
    }

}
